package com.wellsfargo.bm;

import java.util.List;

public class Arrays {

	public  void swap(char[] array, int i, int j){
		char temp=array[i];
		array[i]=array[j];
		array[j]=temp;
	}
	private void swap(int[] array, int i, int j) {
		int temp=array[i];
		array[i]=array[j];
		array[j]=temp;
		
	}
	public void permute(char[] input, int[] rule){
		int prev=0;
		int curr=rule[prev];
		int itr=0;
		
		while(itr<input.length){
			if(prev==curr){
				prev=itr;
				curr=rule[prev];
			}
			swap(input, prev,curr);
			swap(rule,prev,curr);
			curr=rule[prev];
			itr++;
		}
	}
	
	public int[] maxProfit(int[] A,int i, int j){
		int[] arr=new int[j-i+1];
		int minval=A[i];
		int maxProfit=A[i+1]-A[i];
		
		for(int k=i+1;k<=j;k++){
			if(A[k]-minval>maxProfit)
				maxProfit=A[k]-minval;
			if(A[k]<minval)
				minval=A[k];
			arr[k-i]=maxProfit;
		}
		return arr;
	}
	
	public int[][] generateProfitArray(int[] A){
		int[][] profit=new int[A.length][A.length];
		for(int i=0;i<A.length-1;i++){
				int[] p=maxProfit(A,i,A.length-1);
				for(int k=i;k<A.length;k++)
					profit[i][k]=p[k-i];
		}
		System.out.println("done");
		return profit;
	}
	
	public int getMaxProfitKtries(int[] A, int left, int right,int K){
		int[][] profit=generateProfitArray(A);
		return getMaxProfitKtries(A,profit,left,right,K);
	}
	
	public int getMaxProfitKtries(int[] A, int[][] profit,int left, int right,int K){
		int maxPr=0;
		if(right-left<K)
			return Integer.MIN_VALUE;
		if(K==1)
			return profit[left][right];
		else{
			for(int i=left+1;i<right;i++){
				int pr=getMaxProfitKtries(A,profit,left,i,K-1)+getMaxProfitKtries(A,profit,i+1,right,1);
				if(pr>maxPr)
					maxPr=pr;
			}
		}
		return maxPr;
	}
	
	public void getcombinations(int[] A, List<Integer>list,int k, int K,int index){
		if(k==K){
			System.out.println(list);
			return;
		}
		for(int i=index;i<A.length;i++){
			list.add(A[i]);
			getcombinations(A, list,k+1,K,i+1);
			list.remove(list.size()-1);
		}
	}
}
